#include "FFT_test.h"
#include <complex>

#define SWAP(a,b) tempr=(a);(a)=(b);(b)=tempr

static void cpu_fft_complex_line(float *data_line, unsigned int length) {
	int j=0, n = length;
	int mm = n>>1;
    float tempr;
	for (int i=0; i<n; i+=2)
	{
		if (j > i)
		{
			SWAP(data_line[j],data_line[i]);
			SWAP(data_line[j+1],data_line[i+1]);
		}

		int m=mm;
		while (m >= 2 && j >= m)
		{
			j -= m;
			m >>= 1;
		}
		j += m;
	}

	int mmax=2, istep,m,i, isign = 1;
	float theta,wtemp,wpr,wpi,wr,wi,tempi;

	while (n > mmax)
	{
		istep = mmax << 1;
		theta = 6.28318530717959f/(isign*mmax);
		wtemp = sin(0.5f*theta);
		wpr = -2.0f*wtemp*wtemp;
		wpi = sin(theta);
		wr = 1.0;
		wi = 0.0;
    	for (m=0; m<mmax; m+=2)
		{
			for ( i=m; i<n; i+=istep)
			{
				j = i+mmax;
				tempr = wr*data_line[j]-wi*data_line[j+1];
				tempi = wr*data_line[j+1]+wi*data_line[j];
				//data_line[i]+=1.0;
				//data_line[i+1]+=1.0;
				
				data_line[j] = data_line[i]-tempr;
				data_line[j+1] = data_line[i+1]-tempi;
				data_line[i] += tempr;
				data_line[i+1] += tempi;
				
			}
			wr = (wtemp = wr)*wpr - wi*wpi + wr;
			wi = wi*wpr + wtemp*wpi + wi;
		}
		mmax = istep;
	}
}

static void cpu_ifft_complex_line(float *data_line, unsigned int length) {
	int j=0, n = length;
	int mm = n>>1;
    float tempr;
	for (int i=0; i<n; i+=2)
	{
		if (j > i)
		{
			SWAP(data_line[j],data_line[i]);
			SWAP(data_line[j+1],data_line[i+1]);
		}

		int m=mm;
		while (m >= 2 && j >= m)
		{
			j -= m;
			m >>= 1;
		}
		j += m;
	}

	int mmax=2, istep,m,i, isign = -1;
	float theta,wtemp,wpr,wpi,wr,wi,tempi;

	while (n > mmax)
	{
		istep = mmax << 1;
		theta = 6.28318530717959f/(isign*mmax);
		wtemp = sin(0.5f*theta);
		wpr = -2.0f*wtemp*wtemp;
		wpi = sin(theta);
		wr = 1.0;
		wi = 0.0;
    	for (m=0; m<mmax; m+=2)
		{
			for ( i=m; i<n; i+=istep)
			{
				j = i+mmax;
				tempr = wr*data_line[j]-wi*data_line[j+1];
				tempi = wr*data_line[j+1]+wi*data_line[j];
				data_line[j] = data_line[i]-tempr;
				data_line[j+1] = data_line[i+1]-tempi;
				data_line[i] += tempr;
				data_line[i+1] += tempi;
			}
			wr = (wtemp = wr)*wpr - wi*wpi + wr;
			wi = wi*wpr + wtemp*wpi + wi;
		}
		mmax = istep;
	}

	for(i=0;i<n;i++) {
		data_line[i] = data_line[i]/(float)mm;
	}
}

static void cpu_swap_complex_line(float *data_line, unsigned int length) {
	int j=0, n = length;
	int mm = n>>1;
    float tempr;
	for (int i=0; i<n; i+=2)
	{
		if (j > i)
		{
			SWAP(data_line[j],data_line[i]);
			SWAP(data_line[j+1],data_line[i+1]);
		}

		int m=mm;
		while (m >= 2 && j >= m)
		{
			j -= m;
			m >>= 1;
		}
		j += m;
	}
}

float *cpu_fft( float *input_data, unsigned int data_width, unsigned int data_height, FFT_type type ) {
	switch(type) {
		case COMPLEX_FFT:
			for(int i=0;i<data_height;i++) {
				float * index_base = input_data+i*data_width;
				cpu_fft_complex_line(index_base, data_width);
				//cpu_fft_complex_line(index_base, data_width);
				//cpu_swap_complex_line(index_base, data_width);
				//cpu_swap_complex_line(index_base, data_width);
			}
			break;
		case COMPLEX_IFFT:
		default:
			cout<<"not implemented!!!"<<endl;
	}

	return input_data;
}



static float FFT_filter_256 [] = {0.989380f,0.000000f,2.130493f,-0.000008f,4.767273f,-0.000062f,7.499451f,-0.000052f,9.806030f,-0.000038f,12.090698f,-0.000043f,14.628357f,-0.000069f,17.175903f,-0.000077f,19.542908f,-0.000006f,21.904541f,-0.000005f,24.406372f,-0.000059f,26.911682f,-0.000047f,29.302185f,-0.000040f,31.690369f,-0.000070f,34.175659f,-0.000072f,36.662659f,-0.000080f,39.065552f,-0.000020f,41.467163f,-0.000032f,43.942932f,-0.000086f,46.419800f,-0.000058f,48.830139f,-0.000059f,51.239685f,-0.000036f,53.709290f,-0.000065f,56.179810f,-0.000093f,58.595154f,0.000019f,61.009949f,0.000003f,63.475464f,-0.000045f,65.941406f,-0.000046f,68.360413f,-0.000042f,70.778992f,-0.000055f,73.241272f,-0.000079f,75.703979f,-0.000074f,78.125793f,-0.000034f,80.547180f,-0.000057f,83.007141f,-0.000125f,85.467285f,-0.000101f,87.891235f,-0.000094f,90.314880f,-0.000122f,92.772888f,-0.000152f,95.231140f,-0.000154f,97.656738f,-0.000082f,100.082214f,-0.000057f,102.538574f,-0.000136f,104.995300f,-0.000120f,107.422302f,-0.000091f,109.849121f,-0.000116f,112.304321f,-0.000147f,114.759674f,-0.000129f,117.187866f,-0.000074f,119.615936f,-0.000084f,122.070068f,-0.000138f,124.524292f,-0.000121f,126.953430f,-0.000122f,129.382446f,-0.000107f,131.835632f,-0.000145f,134.289001f,-0.000145f,136.718964f,-0.000077f,139.148895f,-0.000124f,141.601318f,-0.000137f,144.053833f,-0.000151f,146.484497f,-0.000116f,148.915131f,-0.000101f,151.366882f,-0.000129f,153.818695f,-0.000148f,156.250061f,-0.000070f,158.681335f,-0.000072f,161.132538f,-0.000139f,163.583801f,-0.000124f,166.015656f,-0.000080f,168.447510f,-0.000113f,170.898163f,-0.000122f,173.348907f,-0.000134f,175.781281f,-0.000069f,178.213654f,-0.000066f,180.663849f,-0.000113f,183.114105f,-0.000124f,185.546906f,-0.000115f,187.979614f,-0.000134f,190.429413f,-0.000176f,192.879242f,-0.000159f,195.312531f,-0.000092f,197.745728f,-0.000151f,200.195099f,-0.000203f,202.644592f,-0.000165f,205.078186f,-0.000187f,207.511688f,-0.000167f,209.960693f,-0.000215f,212.409851f,-0.000248f,214.843750f,-0.000137f,217.277649f,-0.000170f,219.726349f,-0.000225f,222.175171f,-0.000189f,224.609314f,-0.000156f,227.043457f,-0.000174f,229.491913f,-0.000202f,231.940430f,-0.000184f,234.374908f,-0.000166f,236.809357f,-0.000185f,239.257568f,-0.000245f,241.705841f,-0.000253f,244.140533f,-0.000210f,246.575226f,-0.000248f,249.023193f,-0.000239f,251.471252f,-0.000249f,253.906158f,-0.000201f,256.341156f,-0.000224f,258.788849f,-0.000261f,261.236694f,-0.000260f,263.671783f,-0.000239f,266.106903f,-0.000254f,268.554504f,-0.000256f,271.002075f,-0.000284f,273.437439f,-0.000212f,275.872772f,-0.000230f,278.320099f,-0.000302f,280.767578f,-0.000263f,283.203033f,-0.000246f,285.638550f,-0.000247f,288.085724f,-0.000254f,290.533020f,-0.000277f,292.968689f,-0.000223f,295.404327f,-0.000246f,297.851379f,-0.000275f,300.298523f,-0.000303f,302.734283f,-0.000227f,305.170074f,-0.000227f,307.617004f,-0.000301f,310.063934f,-0.000234f,312.499908f,-0.000146f,314.935883f,-0.000149f,317.382629f,-0.000208f,319.829468f,-0.000212f,322.265533f,-0.000127f,324.701599f,-0.000185f,327.148224f,-0.000200f,329.594940f,-0.000229f,332.031158f,-0.000156f,334.467377f,-0.000192f,336.913910f,-0.000207f,339.360504f,-0.000217f,341.796783f,-0.000159f,344.233063f,-0.000196f,346.679504f,-0.000212f,349.125977f,-0.000206f,351.562439f,-0.000164f,353.998840f,-0.000195f,356.445129f,-0.000207f,358.891541f,-0.000220f,361.328033f,-0.000217f,363.764557f,-0.000162f,366.210785f,-0.000186f,368.657043f,-0.000255f,371.093689f,-0.000137f,373.530304f,-0.000145f,375.976410f,-0.000194f,378.422607f,-0.000211f,380.859253f,-0.000151f,383.295929f,-0.000187f,385.742004f,-0.000181f,388.188080f,-0.000174f,390.624878f,-0.000168f,393.061584f,-0.000148f,395.507568f,-0.000203f,397.953644f,-0.000202f,400.390442f,-0.000165f,402.827271f,-0.000217f,405.273254f,-0.000215f,407.719177f,-0.000211f,410.156128f,-0.000158f,412.593079f,-0.000202f,415.038849f,-0.000209f,417.484802f,-0.000214f,419.921753f,-0.000149f,422.358704f,-0.000161f,424.804504f,-0.000219f,427.250305f,-0.000175f,429.687378f,-0.000153f,432.124420f,-0.000184f,434.570129f,-0.000249f,437.015900f,-0.000224f,439.453003f,-0.000188f,441.890076f,-0.000207f,444.335754f,-0.000197f,446.781433f,-0.000193f,449.218628f,-0.000158f,451.655762f,-0.000179f,454.101349f,-0.000180f,456.547058f,-0.000211f,458.984192f,-0.000126f,461.421387f,-0.000104f,463.866943f,-0.000144f,466.312592f,-0.000099f,468.749847f,-0.000084f,471.187073f,-0.000080f,473.632629f,-0.000168f,476.078186f,-0.000141f,478.515472f,-0.000086f,480.952728f,-0.000126f,483.398254f,-0.000148f,485.843781f,-0.000137f,488.281128f,-0.000085f,490.718445f,-0.000109f,493.163879f,-0.000127f,495.609406f,-0.000160f,498.046692f,-0.000101f,500.484039f,-0.000126f,502.929443f,-0.000151f,505.374939f,-0.000129f,507.812378f,-0.000102f,510.249695f,-0.000116f,512.695129f,-0.000133f,515.140564f,-0.000128f,517.577942f,-0.000147f,520.015381f,-0.000128f,522.460693f,-0.000121f,524.906128f,-0.000146f,527.343628f,-0.000081f,529.781006f,-0.000097f,532.226379f,-0.000150f,534.671753f,-0.000174f,537.109192f,-0.000060f,539.546631f,-0.000088f,541.991943f,-0.000083f,544.437317f,-0.000080f,546.874817f,-0.000023f,549.312256f,-0.000065f,551.757507f,-0.000115f,554.202881f,-0.000113f,556.640381f,-0.000064f,559.077881f,-0.000065f,561.523193f,-0.000082f,563.968506f,-0.000116f,566.406067f,-0.000073f,568.843567f,-0.000149f,571.288818f,-0.000112f,573.734131f,-0.000105f,576.171631f,-0.000054f,578.609131f,-0.000050f,581.054382f,-0.000082f,583.499695f,-0.000049f,585.937317f,-0.000092f,588.374817f,-0.000106f,590.820068f,-0.000115f,593.265381f,-0.000100f,595.702881f,-0.000057f,598.140442f,-0.000082f,600.585693f,-0.000039f,603.030945f,-0.000070f,605.468567f,-0.000082f,607.906067f,-0.000095f,610.351318f,-0.000045f,612.796631f,-0.000150f,615.234131f,-0.000023f,617.671692f,-0.000031f,620.116882f,-0.000107f,622.562195f,0.000034f,625.000000f,0.000000f,627.437561f,0.000035f,629.882751f,-0.000076f,632.328064f,-0.000060f,634.765625f,0.000010f,637.203125f,-0.000055f,639.648376f,-0.000041f,642.093628f,-0.000090f,644.531250f,-0.000012f,646.968811f,-0.000063f,649.414001f,-0.000064f,651.859314f,-0.000074f,654.296875f,-0.000019f,656.734375f,-0.000030f,659.179626f,-0.000048f,661.624939f,-0.000064f,664.062500f,-0.000044f,666.500000f,-0.000068f,668.945251f,-0.000045f,671.390564f,-0.000098f,673.828064f,-0.000070f,676.265625f,-0.000056f,678.710876f,-0.000038f,681.156189f,-0.000101f,683.593750f,-0.000012f,686.031250f,-0.000035f,688.476563f,-0.000065f,690.921875f,-0.000078f,693.359314f,0.000016f,695.796814f,0.000001f,698.242126f,0.000023f,700.687500f,0.000021f,703.124939f,0.000039f,705.562378f,0.000039f,708.007690f,0.000023f,710.453064f,-0.000018f,712.890503f,0.000030f,715.328003f,0.000002f,717.773315f,-0.000018f,720.218689f,0.000010f,722.656189f,0.000011f,725.093628f,-0.000018f,727.538940f,-0.000023f,729.984375f,-0.000044f,732.421753f,0.000034f,734.859131f,0.000038f,737.304565f,-0.000010f,739.750000f,0.000018f,742.187439f,0.000009f,744.624817f,-0.000021f,747.070190f,-0.000018f,749.515686f,-0.000024f,751.953003f,0.000019f,754.390381f,-0.000006f,756.835815f,0.000023f,759.281250f,0.000023f,761.718628f,0.000041f,764.155945f,0.000012f,766.601440f,0.000034f,769.046997f,-0.000008f,771.484253f,0.000095f,773.921509f,0.000095f,776.367065f,0.000100f,778.812622f,0.000124f,781.249878f,0.000119f,783.687134f,0.000119f,786.132690f,0.000092f,788.578308f,0.000068f,791.015503f,0.000116f,793.452698f,0.000076f,795.898315f,0.000096f,798.343994f,0.000090f,800.781189f,0.000091f,803.218323f,0.000073f,805.663940f,0.000084f,808.109680f,0.000050f,810.546753f,0.000114f,812.983826f,0.000106f,815.429565f,0.000078f,817.875305f,0.000090f,820.312378f,0.000096f,822.749390f,0.000082f,825.195129f,0.000112f,827.640991f,0.000071f,830.077942f,0.000077f,832.514893f,0.000093f,834.960754f,0.000122f,837.406616f,0.000093f,839.843628f,0.000109f,842.280518f,0.000101f,844.726440f,0.000075f,847.172363f,0.000055f,849.609192f,0.000136f,852.046021f,0.000144f,854.492065f,0.000155f,856.938049f,0.000178f,859.374817f,0.000170f,861.811584f,0.000195f,864.257629f,0.000189f,866.703735f,0.000168f,869.140381f,0.000220f,871.577087f,0.000179f,874.023254f,0.000205f,876.469360f,0.000215f,878.906067f,0.000185f,881.342651f,0.000118f,883.788879f,0.000173f,886.235107f,0.000184f,888.671631f,0.000213f,891.108154f,0.000211f,893.554443f,0.000221f,896.000854f,0.000219f,898.437256f,0.000181f,900.873657f,0.000168f,903.320068f,0.000179f,905.766541f,0.000185f,908.202881f,0.000232f,910.639160f,0.000195f,913.085693f,0.000242f,915.532288f,0.000224f,917.968506f,0.000185f,920.404785f,0.000202f,922.851318f,0.000226f,925.298035f,0.000186f,927.734131f,0.000311f,930.170166f,0.000271f,932.616943f,0.000267f,935.063782f,0.000327f,937.499878f,0.000278f,939.935791f,0.000290f,942.382690f,0.000267f,944.829590f,0.000268f,947.265442f,0.000315f,949.701233f,0.000264f,952.148315f,0.000291f,954.595398f,0.000289f,957.031067f,0.000274f,959.466675f,0.000254f,961.913940f,0.000306f,964.361145f,0.000263f,966.796631f,0.000309f,969.232178f,0.000297f,971.679565f,0.000300f,974.126953f,0.000311f,976.562256f,0.000280f,978.997559f,0.000268f,981.445129f,0.000304f,983.892700f,0.000253f,986.327881f,0.000252f,988.763062f,0.000274f,991.210815f,0.000300f,993.658508f,0.000309f,996.093567f,0.000256f,998.528442f,0.000300f,1000.976440f,0.000301f,1003.424438f,0.000294f,1005.859131f,0.000360f,1008.293823f,0.000357f,1010.742065f,0.000389f,1013.190308f,0.000405f,1015.624756f,0.000414f,1018.059204f,0.000430f,1020.507690f,0.000435f,1022.956177f,0.000436f,1025.390381f,0.000479f,1027.824463f,0.000446f,1030.273315f,0.000429f,1032.722046f,0.000471f,1035.156006f,0.000433f,1037.589844f,0.000383f,1040.038940f,0.000466f,1042.488037f,0.000420f,1044.921631f,0.000468f,1047.355225f,0.000480f,1049.804565f,0.000476f,1052.254028f,0.000488f,1054.687256f,0.000440f,1057.120361f,0.000435f,1059.570190f,0.000462f,1062.020020f,0.000480f,1064.452759f,0.000515f,1066.885620f,0.000484f,1069.335815f,0.000538f,1071.786011f,0.000547f,1074.218506f,0.000494f,1076.650757f,0.000499f,1079.101563f,0.000541f,1081.552124f,0.000497f,1083.984009f,0.000552f,1086.415894f,0.000567f,1088.867188f,0.000582f,1091.318359f,0.000582f,1093.749634f,0.000535f,1096.180908f,0.000540f,1098.632813f,0.000577f,1101.084595f,0.000568f,1103.515259f,0.000574f,1105.945923f,0.000584f,1108.398438f,0.000577f,1110.850830f,0.000604f,1113.280884f,0.000538f,1115.710815f,0.000551f,1118.164063f,0.000603f,1120.617310f,0.000557f,1123.046387f,0.000629f,1125.475586f,0.000624f,1127.929688f,0.000649f,1130.383911f,0.000638f,1132.811890f,0.000579f,1135.239990f,0.000595f,1137.695313f,0.000647f,1140.150635f,0.000600f,1142.577393f,0.000636f,1145.004395f,0.000630f,1147.461182f,0.000701f,1149.917480f,0.000694f,1152.343018f,0.000613f,1154.768555f,0.000633f,1157.226807f,0.000661f,1159.684814f,0.000613f,1162.108398f,0.000689f,1164.532471f,0.000707f,1166.992676f,0.000712f,1169.452637f,0.000700f,1171.874023f,0.000715f,1174.295776f,0.000732f,1176.758423f,0.000782f,1179.220703f,0.000757f,1181.639404f,0.000763f,1184.058350f,0.000785f,1186.524292f,0.000791f,1188.989746f,0.000802f,1191.404541f,0.000736f,1193.819946f,0.000704f,1196.290283f,0.000782f,1198.760010f,0.000754f,1201.169556f,0.000780f,1203.579956f,0.000785f,1206.056885f,0.000818f,1208.532593f,0.000813f,1210.934082f,0.000749f,1213.336914f,0.000757f,1215.823975f,0.000829f,1218.309204f,0.000785f,1220.697388f,0.000827f,1223.088013f,0.000793f,1225.593262f,0.000835f,1228.095093f,0.000827f,1230.456787f,0.000759f,1232.823730f,0.000776f,1235.371216f,0.000825f,1237.908936f,0.000807f,1240.193604f,0.000847f,1242.500244f,0.000838f,1245.232422f,0.000882f,1247.869141f,0.000882f,1249.010620f,0.000000f,1247.869507f,0.000008f,1245.232666f,0.000062f,1242.500488f,0.000052f,1240.193970f,0.000038f,1237.909302f,0.000043f,1235.371582f,0.000069f,1232.824097f,0.000077f,1230.457031f,0.000006f,1228.095459f,0.000005f,1225.593628f,0.000059f,1223.088379f,0.000047f,1220.697754f,0.000040f,1218.309570f,0.000070f,1215.824341f,0.000072f,1213.337402f,0.000080f,1210.934448f,0.000020f,1208.532837f,0.000032f,1206.057129f,0.000086f,1203.580200f,0.000058f,1201.169922f,0.000059f,1198.760254f,0.000036f,1196.290771f,0.000065f,1193.820190f,0.000093f,1191.404785f,-0.000019f,1188.989990f,-0.000003f,1186.524536f,0.000045f,1184.058594f,0.000046f,1181.639648f,0.000042f,1179.220947f,0.000055f,1176.758789f,0.000079f,1174.296021f,0.000074f,1171.874268f,0.000034f,1169.452881f,0.000057f,1166.992920f,0.000125f,1164.532715f,0.000101f,1162.108765f,0.000094f,1159.685059f,0.000122f,1157.227051f,0.000152f,1154.768799f,0.000154f,1152.343262f,0.000082f,1149.917725f,0.000057f,1147.461426f,0.000136f,1145.004639f,0.000120f,1142.577637f,0.000091f,1140.150879f,0.000116f,1137.695679f,0.000147f,1135.240356f,0.000129f,1132.812134f,0.000074f,1130.384033f,0.000084f,1127.929932f,0.000138f,1125.475708f,0.000121f,1123.046631f,0.000122f,1120.617554f,0.000107f,1118.164307f,0.000145f,1115.710938f,0.000145f,1113.281006f,0.000077f,1110.851074f,0.000124f,1108.398682f,0.000137f,1105.946167f,0.000151f,1103.515503f,0.000116f,1101.084839f,0.000101f,1098.633057f,0.000129f,1096.181274f,0.000148f,1093.750000f,0.000070f,1091.318604f,0.000072f,1088.867432f,0.000139f,1086.416260f,0.000124f,1083.984375f,0.000080f,1081.552490f,0.000113f,1079.101807f,0.000122f,1076.651123f,0.000134f,1074.218750f,0.000069f,1071.786377f,0.000066f,1069.336182f,0.000113f,1066.885864f,0.000124f,1064.453125f,0.000115f,1062.020386f,0.000134f,1059.570557f,0.000176f,1057.120728f,0.000159f,1054.687500f,0.000092f,1052.254272f,0.000151f,1049.804932f,0.000203f,1047.355469f,0.000165f,1044.921875f,0.000187f,1042.488281f,0.000167f,1040.039307f,0.000215f,1037.590088f,0.000248f,1035.156250f,0.000137f,1032.722412f,0.000170f,1030.273682f,0.000225f,1027.824829f,0.000189f,1025.390625f,0.000156f,1022.956543f,0.000174f,1020.508057f,0.000202f,1018.059570f,0.000184f,1015.625122f,0.000166f,1013.190674f,0.000185f,1010.742432f,0.000245f,1008.294189f,0.000253f,1005.859497f,0.000210f,1003.424805f,0.000248f,1000.976807f,0.000239f,998.528748f,0.000249f,996.093872f,0.000201f,993.658813f,0.000224f,991.211182f,0.000261f,988.763306f,0.000260f,986.328247f,0.000239f,983.893066f,0.000254f,981.445496f,0.000256f,978.997925f,0.000284f,976.562561f,0.000212f,974.127197f,0.000230f,971.679932f,0.000302f,969.232422f,0.000263f,966.796997f,0.000246f,964.361450f,0.000247f,961.914307f,0.000254f,959.466980f,0.000277f,957.031311f,0.000223f,954.595703f,0.000246f,952.148621f,0.000275f,949.701477f,0.000303f,947.265747f,0.000227f,944.829956f,0.000227f,942.382996f,0.000301f,939.936035f,0.000234f,937.500122f,0.000146f,935.064087f,0.000149f,932.617371f,0.000208f,930.170532f,0.000212f,927.734497f,0.000127f,925.298401f,0.000185f,922.851807f,0.000200f,920.405029f,0.000229f,917.968872f,0.000156f,915.532593f,0.000192f,913.086060f,0.000207f,910.639526f,0.000217f,908.203247f,0.000159f,905.766968f,0.000196f,903.320496f,0.000212f,900.874023f,0.000206f,898.437561f,0.000164f,896.001160f,0.000195f,893.554871f,0.000207f,891.108459f,0.000220f,888.671997f,0.000217f,886.235474f,0.000162f,883.789185f,0.000186f,881.342957f,0.000255f,878.906311f,0.000137f,876.469727f,0.000145f,874.023560f,0.000194f,871.577393f,0.000211f,869.140747f,0.000151f,866.704102f,0.000187f,864.257996f,0.000181f,861.811890f,0.000174f,859.375122f,0.000168f,856.938416f,0.000148f,854.492432f,0.000203f,852.046387f,0.000202f,849.609558f,0.000165f,847.172729f,0.000217f,844.726746f,0.000215f,842.280823f,0.000211f,839.843872f,0.000158f,837.406921f,0.000202f,834.961182f,0.000209f,832.515198f,0.000214f,830.078247f,0.000149f,827.641296f,0.000161f,825.195496f,0.000219f,822.749695f,0.000175f,820.312622f,0.000153f,817.875610f,0.000184f,815.429871f,0.000249f,812.984131f,0.000224f,810.546997f,0.000188f,808.109924f,0.000207f,805.664246f,0.000197f,803.218567f,0.000193f,800.781372f,0.000158f,798.344238f,0.000179f,795.898682f,0.000180f,793.452942f,0.000211f,791.015808f,0.000126f,788.578613f,0.000104f,786.133057f,0.000144f,783.687378f,0.000099f,781.250122f,0.000084f,778.812927f,0.000080f,776.367371f,0.000168f,773.921814f,0.000141f,771.484497f,0.000086f,769.047241f,0.000126f,766.601746f,0.000148f,764.156250f,0.000137f,761.718872f,0.000085f,759.281555f,0.000109f,756.836121f,0.000127f,754.390625f,0.000160f,751.953308f,0.000101f,749.515991f,0.000126f,747.070557f,0.000151f,744.625061f,0.000129f,742.187622f,0.000102f,739.750305f,0.000116f,737.304871f,0.000133f,734.859436f,0.000128f,732.422058f,0.000147f,729.984619f,0.000128f,727.539307f,0.000121f,725.093872f,0.000146f,722.656372f,0.000081f,720.218994f,0.000097f,717.773621f,0.000150f,715.328247f,0.000174f,712.890808f,0.000060f,710.453369f,0.000088f,708.008057f,0.000083f,705.562683f,0.000080f,703.125183f,0.000023f,700.687744f,0.000065f,698.242493f,0.000115f,695.797119f,0.000113f,693.359619f,0.000064f,690.922119f,0.000065f,688.476807f,0.000082f,686.031494f,0.000116f,683.593933f,0.000073f,681.156433f,0.000149f,678.711182f,0.000112f,676.265869f,0.000105f,673.828369f,0.000054f,671.390869f,0.000050f,668.945618f,0.000082f,666.500305f,0.000049f,664.062683f,0.000092f,661.625183f,0.000106f,659.179932f,0.000115f,656.734619f,0.000100f,654.297119f,0.000057f,651.859558f,0.000082f,649.414307f,0.000039f,646.969055f,0.000070f,644.531433f,0.000082f,642.093933f,0.000095f,639.648682f,0.000045f,637.203369f,0.000150f,634.765869f,0.000023f,632.328308f,0.000031f,629.883118f,0.000107f,627.437805f,-0.000034f,625.000000f,0.000000f,622.562439f,-0.000035f,620.117249f,0.000076f,617.671936f,0.000060f,615.234375f,-0.000010f,612.796875f,0.000055f,610.351624f,0.000041f,607.906372f,0.000090f,605.468750f,0.000012f,603.031189f,0.000063f,600.585999f,0.000064f,598.140686f,0.000074f,595.703125f,0.000019f,593.265625f,0.000030f,590.820374f,0.000048f,588.375061f,0.000064f,585.937500f,0.000044f,583.500000f,0.000068f,581.054749f,0.000045f,578.609436f,0.000098f,576.171936f,0.000070f,573.734375f,0.000056f,571.289124f,0.000038f,568.843811f,0.000101f,566.406250f,0.000012f,563.968750f,0.000035f,561.523438f,0.000065f,559.078125f,0.000078f,556.640686f,-0.000016f,554.203186f,-0.000001f,551.757874f,-0.000023f,549.312500f,-0.000021f,546.875061f,-0.000039f,544.437622f,-0.000039f,541.992310f,-0.000023f,539.546936f,0.000018f,537.109497f,-0.000030f,534.671997f,-0.000002f,532.226685f,0.000018f,529.781311f,-0.000010f,527.343811f,-0.000011f,524.906372f,0.000018f,522.461060f,0.000023f,520.015625f,0.000044f,517.578247f,-0.000034f,515.140869f,-0.000038f,512.695435f,0.000010f,510.250000f,-0.000018f,507.812561f,-0.000009f,505.375214f,0.000021f,502.929810f,0.000018f,500.484344f,0.000024f,498.047028f,-0.000019f,495.609650f,0.000006f,493.164185f,-0.000023f,490.718719f,-0.000023f,488.281342f,-0.000041f,485.844055f,-0.000012f,483.398560f,-0.000034f,480.953003f,0.000008f,478.515747f,-0.000095f,476.078491f,-0.000095f,473.632935f,-0.000100f,471.187378f,-0.000124f,468.750092f,-0.000119f,466.312866f,-0.000119f,463.867310f,-0.000092f,461.421692f,-0.000068f,458.984497f,-0.000116f,456.547302f,-0.000076f,454.101685f,-0.000096f,451.656006f,-0.000090f,449.218811f,-0.000091f,446.781677f,-0.000073f,444.336029f,-0.000084f,441.890320f,-0.000050f,439.453247f,-0.000114f,437.016174f,-0.000106f,434.570435f,-0.000078f,432.124695f,-0.000090f,429.687622f,-0.000096f,427.250610f,-0.000082f,424.804871f,-0.000112f,422.359009f,-0.000071f,419.922058f,-0.000077f,417.485077f,-0.000093f,415.039246f,-0.000122f,412.593384f,-0.000093f,410.156372f,-0.000109f,407.719513f,-0.000101f,405.273590f,-0.000075f,402.827637f,-0.000055f,400.390808f,-0.000136f,397.953979f,-0.000144f,395.507935f,-0.000155f,393.061951f,-0.000178f,390.625183f,-0.000170f,388.188416f,-0.000195f,385.742371f,-0.000189f,383.296265f,-0.000168f,380.859619f,-0.000220f,378.422913f,-0.000179f,375.976746f,-0.000205f,373.530609f,-0.000215f,371.093933f,-0.000185f,368.657349f,-0.000118f,366.211121f,-0.000173f,363.764893f,-0.000184f,361.328369f,-0.000213f,358.891876f,-0.000211f,356.445526f,-0.000221f,353.999176f,-0.000219f,351.562714f,-0.000181f,349.126312f,-0.000168f,346.679901f,-0.000179f,344.233459f,-0.000185f,341.797150f,-0.000232f,339.360840f,-0.000195f,336.914276f,-0.000242f,334.467712f,-0.000224f,332.031464f,-0.000185f,329.595245f,-0.000202f,327.148651f,-0.000226f,324.701965f,-0.000186f,322.265900f,-0.000311f,319.829803f,-0.000271f,317.383026f,-0.000267f,314.936218f,-0.000327f,312.500153f,-0.000278f,310.064240f,-0.000290f,307.617310f,-0.000267f,305.170410f,-0.000268f,302.734558f,-0.000315f,300.298767f,-0.000264f,297.851654f,-0.000291f,295.404602f,-0.000289f,292.968933f,-0.000274f,290.533295f,-0.000254f,288.086090f,-0.000306f,285.638855f,-0.000263f,283.203339f,-0.000309f,280.767853f,-0.000297f,278.320435f,-0.000300f,275.873077f,-0.000311f,273.437714f,-0.000280f,271.002411f,-0.000268f,268.554871f,-0.000304f,266.107300f,-0.000253f,263.672150f,-0.000252f,261.236969f,-0.000274f,258.789185f,-0.000300f,256.341492f,-0.000309f,253.906433f,-0.000256f,251.471588f,-0.000300f,249.023529f,-0.000301f,246.575562f,-0.000294f,244.140869f,-0.000360f,241.706146f,-0.000357f,239.257904f,-0.000389f,236.809662f,-0.000405f,234.375244f,-0.000414f,231.940765f,-0.000430f,229.492310f,-0.000435f,227.043854f,-0.000436f,224.609650f,-0.000479f,222.175476f,-0.000446f,219.726685f,-0.000429f,217.277954f,-0.000471f,214.843994f,-0.000433f,212.410126f,-0.000383f,209.961060f,-0.000466f,207.511993f,-0.000420f,205.078400f,-0.000468f,202.644806f,-0.000480f,200.195435f,-0.000476f,197.746002f,-0.000488f,195.312775f,-0.000440f,192.879608f,-0.000435f,190.429810f,-0.000462f,187.980011f,-0.000480f,185.547241f,-0.000515f,183.114380f,-0.000484f,180.664185f,-0.000538f,178.213989f,-0.000547f,175.781555f,-0.000494f,173.349213f,-0.000499f,170.898499f,-0.000541f,168.447876f,-0.000497f,166.015961f,-0.000552f,163.584076f,-0.000567f,161.132843f,-0.000582f,158.681671f,-0.000582f,156.250336f,-0.000535f,153.819031f,-0.000540f,151.367188f,-0.000577f,148.915405f,-0.000568f,146.484772f,-0.000574f,144.054077f,-0.000584f,141.601532f,-0.000577f,139.149139f,-0.000604f,136.719147f,-0.000538f,134.289215f,-0.000551f,131.835938f,-0.000603f,129.382660f,-0.000557f,126.953644f,-0.000629f,124.524475f,-0.000624f,122.070251f,-0.000649f,119.616119f,-0.000638f,117.188080f,-0.000579f,114.759949f,-0.000595f,112.304626f,-0.000647f,109.849426f,-0.000600f,107.422607f,-0.000636f,104.995544f,-0.000630f,102.538879f,-0.000701f,100.082458f,-0.000694f,97.656982f,-0.000613f,95.231384f,-0.000633f,92.773193f,-0.000661f,90.315186f,-0.000613f,87.891541f,-0.000689f,85.467590f,-0.000707f,83.007385f,-0.000712f,80.547424f,-0.000700f,78.125977f,-0.000715f,75.704224f,-0.000732f,73.241577f,-0.000782f,70.779297f,-0.000757f,68.360596f,-0.000763f,65.941589f,-0.000785f,63.475708f,-0.000791f,61.010315f,-0.000802f,58.595398f,-0.000736f,56.180054f,-0.000704f,53.709656f,-0.000782f,51.239990f,-0.000754f,48.830444f,-0.000780f,46.420044f,-0.000785f,43.943176f,-0.000818f,41.467407f,-0.000813f,39.065857f,-0.000749f,36.663086f,-0.000757f,34.176086f,-0.000829f,31.690796f,-0.000785f,29.302612f,-0.000827f,26.911987f,-0.000793f,24.406738f,-0.000835f,21.904907f,-0.000827f,19.543274f,-0.000759f,17.176270f,-0.000776f,14.628784f,-0.000825f,12.091125f,-0.000807f,9.806335f,-0.000847f,7.499695f,-0.000838f,4.767578f,-0.000882f,2.130798f,-0.000882f};

void CPU_FFT_Manager::cpu_run(float *input_data) {

	cout<<"cpu running ..." << endl;
	//cout<<"sizeof filter is"<<sizeof(FFT_filter_256)<<endl;
	unsigned int fft_line_size = data_desc->get_fft_row();
	float *extended_data_line =  (float *)malloc(fft_line_size*sizeof(float));
	
	unsigned int index_base = 0;
	unsigned int fft_index_base = 0;
	for(int i=0;i<data_desc->projection;i++) {
		for(int j=0;j<data_desc->height;j++) {
			
			//dump_real(input_data, i, data_desc->height, j, data_desc->width, 10 );
			memset(extended_data_line, 0, fft_line_size*sizeof(float));
			index_base = (i*data_desc->height+j)*data_desc->width;
			for(int k=0;k<data_desc->width;k++) {
			    unsigned index = index_base + k;
			    unsigned fft_index = k*2; //real part and integete part
			    extended_data_line[fft_index] = input_data[index];
			}

			//dump_cplx(extended_data_line, 0, data_desc->height, 0, fft_line_size, 512 );
			
			cpu_fft_complex_line(extended_data_line, fft_line_size);
			//cpu_swap_complex_line(extended_data_line, fft_line_size);

			dump_cplx(extended_data_line, 0, data_desc->height, 0, fft_line_size, 2048 );
			//filter
			/*
			for(int k=0;k<fft_line_size;k+=2) {
				extended_data_line[k] *= FFT_filter_256[k];
				extended_data_line[k+1] *= FFT_filter_256[k];
			}
			*/
			//cpu_ifft_complex_line(extended_data_line, fft_line_size);
			
			for(int k=0;k<data_desc->width;k++) {
				unsigned index = index_base + k;
				unsigned fft_index = k*2; //real part and integete part
				result_data[index] = extended_data_line[fft_index];
			}

			//dump_real(result_data, i, data_desc->height, j, data_desc->width, 10 );
		}
	}
	free(extended_data_line);

}


